package problem.ej1;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Vector;

public class Kruskal{
	
	private Vector<Integer> rank = new Vector<Integer>();
	private Vector<Integer> parent = new Vector<Integer>();
	private Integer peso;
	
	public Integer damePeso(){
		Ej1.contador_ej1_kruskal++;
		Ej1.contador_ej1++;
		return this.peso;
	}
	
	//funciones del set
	public void create_set(int x){
		this.rank.set(x, 0);
		this.parent.set(x, x);
		Ej1.contador_ej1_kruskal+=4;
		Ej1.contador_ej1+=4;
	}
	
	public Integer find_set(int x){
		Ej1.contador_ej1_kruskal+=5;
		  Ej1.contador_ej1+=5;
		  if (x != this.parent.elementAt(x)){
			  this.parent.set(x, find_set( this.parent.elementAt(x) ) ) ;
			  Ej1.contador_ej1_kruskal+=5;
			  Ej1.contador_ej1+=5;
		  }
		  Ej1.contador_ej1_kruskal++;
		  Ej1.contador_ej1++;
		  return this.parent.elementAt(x);
	}
	
	public void merge_set(int x, int y) {
		Ej1.contador_ej1_kruskal+=6;
	      Ej1.contador_ej1+=6;
		  if (this.rank.elementAt(x) > this.rank.elementAt(y)){
			  this.parent.set(y, this.parent.elementAt(x));
			  Ej1.contador_ej1_kruskal+=4;
			  Ej1.contador_ej1+=4;
		  }
		  
		  else{
			  this.parent.set(x,this.parent.elementAt(y));
			  Ej1.contador_ej1_kruskal+=4;
			  Ej1.contador_ej1+=4;
		  }
		  Ej1.contador_ej1+=6;
		  Ej1.contador_ej1_kruskal+=6;
		  if (this.rank.elementAt(x) == this.rank.elementAt(y)){
			  this.rank.set(y, this.rank.elementAt(y)+1);
			  Ej1.contador_ej1+=5;
			  Ej1.contador_ej1_kruskal+=5;
		  }
		 
	}
	
	//devuelve el menor peso del eje del camino que me lleva desde el origen al destino: 
	//n: cantidad de vertices totales
	//ejes: ejes del que componen el AGM
	//origen: nodo del cual parte el camionero
	//destino: nodo de llegada del camionero
	public void calcular_peso_camino_maximo(Integer n, LinkedList<Eje> ejes, Integer origen, Integer destino){
		LinkedList<Eje>[] arrayEjes = new LinkedList[n];
		Ej1.contador_ej1+=n;
		Ej1.contador_ej1_calcular_peso+=n;
		
		//inicializo el array de lista de ejes
		Integer i = 0;
		Ej1.contador_ej1+=3;
		Ej1.contador_ej1_calcular_peso+=3;
		while(i<n){
			arrayEjes[i] = new LinkedList<Eje>();
			i++;
			Ej1.contador_ej1_calcular_peso+=4;
			Ej1.contador_ej1+=4;
		}
		
		Iterator<Eje> iterEjes = ejes.iterator();
		Ej1.contador_ej1_calcular_peso+=3;
		Ej1.contador_ej1+=3;
		
		//agrego los ejes al arreglo creado antes
		while(iterEjes.hasNext()){
			Eje eje = iterEjes.next();
			arrayEjes[eje.getDes()].add(eje);
			arrayEjes[eje.getOri()].add(eje);
			Ej1.contador_ej1_calcular_peso+=14;
			Ej1.contador_ej1+=14;
		}
		
		
		
		//calculo la lista de pesos del camino que va de origen a destino
		calcular_peso(n, arrayEjes, origen, destino, -1);
		Ej1.contador_ej1_calcular_peso+=1;
		Ej1.contador_ej1+=1;

	}
	
	public boolean calcular_peso(Integer n, LinkedList<Eje>[] arrayEjes, Integer nodoActual, Integer destino, Integer nodoDeDondeVengo){
		
		Iterator<Eje> iterEje = arrayEjes[nodoActual].iterator();
		Ej1.contador_ej1+=3;
		Ej1.contador_ej1_calcular_peso+=3;
		
		//recorro los ejes del nodo actual
			/*Los casos que pueden suceder son:
			 *que uno de los ejes me conecte con el destino
			 *que no tenga ejes donde conectarme (en realidad en ese caso tiene 1 solo eje que es el que lo conecta con el nodoDeDondeVengo)
			 *que tenga varios ejes para que los recorra
			 */
		Ej1.contador_ej1+=2;
		Ej1.contador_ej1_calcular_peso+=2;
		while(iterEje.hasNext()){
			Eje eje = iterEje.next();
			Ej1.contador_ej1_calcular_peso+=2;
			Ej1.contador_ej1+=2;
			Ej1.contador_ej1_calcular_peso+=11;/*(lo de la guarda del if y la guarda*/
			Ej1.contador_ej1+=11;/*(lo de la guarda del if y la guarda*/
			//si el eje no es el nodo del cual vengo....
			if( ! (eje.getOri().equals(nodoDeDondeVengo)) && ! (eje.getDes().equals(nodoDeDondeVengo)) ){
				
				Ej1.contador_ej1_calcular_peso+=7;
				Ej1.contador_ej1+=7;
				//veo si es el eje que me une al nodo destino:
				if(eje.getOri().equals(destino) || eje.getDes().equals(destino)){
					//pongo el peso del eje que me lleva al destino como actual minimo y retorno true para indicar que encontre el camino y no seguir recorriendo los ejes.
					Ej1.contador_ej1_calcular_peso+=4;
					Ej1.contador_ej1+=4;
					this.peso = eje.getPeso();
					//System.out.println("el peso de destino : "+peso+" -");
					return true;
				}
				//llamo recursivamente sobre el eje
				//si el origen es el nodo actual entonces llamo recursivamente sobre eje.getDes()
				Ej1.contador_ej1_calcular_peso+=3;
				Ej1.contador_ej1+=3;
				if(eje.getOri().equals(nodoActual)){
					Ej1.contador_ej1_calcular_peso+=3;
					Ej1.contador_ej1+=3;
					if( calcular_peso(n, arrayEjes, eje.getDes(), destino, nodoActual )){
						Ej1.contador_ej1_calcular_peso+=3;
						Ej1.contador_ej1+=3;
						//si el peso de este eje es menor al peso que que suponia como minimo (el resultante de llamar a "calcular_peso" en la guarda del if) => lo cambio por el peso de este eje
						if(this.peso> eje.getPeso()){
							Ej1.contador_ej1_calcular_peso+=2;
							Ej1.contador_ej1+=2;
							this.peso = eje.getPeso();
						}
						Ej1.contador_ej1_calcular_peso+=1;
						Ej1.contador_ej1+=1;
						return true;
					}
				}else {
					Ej1.contador_ej1_calcular_peso+=4;
					Ej1.contador_ej1+=4;
					if( calcular_peso(n, arrayEjes, eje.getOri(), destino, nodoActual )){
						//si el peso de este eje es menor al peso que que suponia como minimo (el resultante de llamar a "calcular_peso" en la guarda del if) => lo cambio por el peso de este eje
						Ej1.contador_ej1_calcular_peso+=3;
						Ej1.contador_ej1+=3;
						if(this.peso> eje.getPeso()){
							Ej1.contador_ej1_calcular_peso+=2;
							Ej1.contador_ej1+=2;
							this.peso = eje.getPeso();
						}
						Ej1.contador_ej1_calcular_peso+=1;
						Ej1.contador_ej1+=1;
						return true;
					}
				}
			
			}
		}
		//retorno falso si recorri todos los ejes y no encontre un camino al destino
		Ej1.contador_ej1_calcular_peso+=1;
		Ej1.contador_ej1+=1;
		return false;
	}
	
	//constructor por defecto (usado para testeo)
	public Kruskal(){
	}
	
	//funcion principal(constructor de la clase Kruskal):
	//la idea es que reciba la cantidad de vertices como el "n" y todos los ejes como una trupla< Nodo_A, Peso_De_A_a_B, Nodo_B>
	public Kruskal(Integer n, Vector<Eje> listaEjes, Integer origen, Integer destino){
		this.rank.setSize(n);
		Ej1.contador_ej1_kruskal+=n;
		Ej1.contador_ej1+=n;
		this.parent.setSize(n);
		Ej1.contador_ej1_kruskal+=n;
		Ej1.contador_ej1+=n;
		this.peso = -1;
		Ej1.contador_ej1_kruskal+=1;
		Ej1.contador_ej1+=1;
		
		LinkedList<Eje> ejesDelAgM = new LinkedList<Eje>();
		Integer remaining = n-1;
		Ej1.contador_ej1+=2;
		Ej1.contador_ej1_kruskal+=2;
		
		//la lista de ejes la tengo ordenada de mayor a menor peso en los ejes
		for(int i=0; i<n;i++) create_set(i);
		Ej1.contador_ej1+=n+2;
		Ej1.contador_ej1_kruskal+=n+2;

		
		Iterator<Eje> iterEje = listaEjes.iterator();
		Ej1.contador_ej1_kruskal+=1;
		Ej1.contador_ej1+=1;
		
		Ej1.contador_ej1_kruskal+=2;
		Ej1.contador_ej1+=2;
		while(iterEje.hasNext()){
			Eje eje = iterEje.next();
			Ej1.contador_ej1_kruskal+=2+4+4+3;
			Ej1.contador_ej1+=2+4+4+3;
	
			Integer u = new Integer(find_set(eje.getDes() ));
			Integer v = new Integer(find_set(eje.getOri() ));
			if(!u.equals(v)){
				Ej1.contador_ej1_kruskal+=1+1+1+1;
				Ej1.contador_ej1+=1+1+1+1;
				merge_set(u, v);  //si no tienen el mismo padre entonces los uno.
				ejesDelAgM.add(eje);
				
				remaining--;
				if(remaining == 0) break;
			}
		}
		if (remaining != 0) { System.out.println("HA FALLADO WARNING WARNING WARNING"); System.exit(1); } //si cae ac� NO FUNCA UNA MIERDA !
		
		/*
		 *muestra la lista de ejes del agm
		Iterator<Eje> iterPiola = ejesDelAgM.iterator();
		while(iterPiola.hasNext()){
			iterPiola.next().mostrar();
		}*/
		
		calcular_peso_camino_maximo(n, ejesDelAgM ,origen, destino);
		Ej1.contador_ej1_kruskal+=1;
		Ej1.contador_ej1+=1;
		
	}

}
